package data_structure.mooc;

import data_structure.helper.ArrayGenerator;
import data_structure.helper.SortingHelper;

public class CountSort {

    private CountSort() {

    }

    public static void sort(Integer []arr,int range){

        //计数排序是非比较，稳定的排序方式，不是原地排序
        //确定范围
        //记录数据出现的次数
        //用一个额外的数组来存储数组中不同元素的上下界，其中上界可以取到，下界取不到,元素个数为r+1
        //用一个temp数组辅助排序
        int []cnt=new int[range];
        int [] index=new int[range+1];
        int []temp=new int [arr.length];

        for (int el : arr) {
            cnt[el]++;
        }

        //index[i,i+1)范围中的元素为i
        for(int i=0;i+1<index.length; i++){
            index[i+1]=index[i]+cnt[i];
        }

        //用temp数组辅助排序
        for(int i=0;i<arr.length; i++){
            temp[index[arr[i]]]=arr[i];
            index[arr[i]]++;
        }

        for (int i = 0; i <arr.length ; i++) {
            arr[i]=temp[i];
        }

    }
//    public static void main(String[] args) {
//        Integer []arr=ArrayGenerator.generateNormalArray (1000,5);
//        CountSort.sort (arr,5);
//        for (Integer integer : arr) {
//            System.out.println(integer);
//        }
//    }
}
